Pseudorandom Permutations

A pseudorandom permutation (PRP) is a specific type of pseudorandom function (PRF).

A *pseudorandom permutation* $\textit{PRP}(\textit{idb}: \textbf{str}[l]) \to \textbf{str}[l]$ is a pseudorandom function which satisfies the following properties:

- The output length $l_{\text{out}}$ is the same as the input length $l$, i.e. $l_{\text{out}} = l$.
- The function $\textit{PRP}$ is a permutation of $\{0,1\}^l$, i.e. the function is bijective.
- The function is *reversible*, i.e. there is an efficient algorithm $\textit{RevPRP}$ such that $\textit{RevPRP}(\textit{PRP}(x)) = x$ for all $x \in \{0,1\}^l$.

A pseudorandom permutation is a subtype of a pseudorandom function where the output length matches the input length $l$. Furthermore, a PRP is a [bijection](../Mathematical%20Prerequisites.md#admonition-injection-surjection-and-bijection) which maps each binary string of length $l$ to a single binary string, also of length $l$. Finally, the PRP must be reversible in the sense that there is an efficient algorithm which can recover the input that was passed to the PRP in order to obtain a specific output.

The input/output length is often called the *block length*.

Pseudorandom permutation are useful in the construction of block ciphers because they have inputs and outputs of the same length.

Theoretical Implementation - PRPs from PRFs

Since PRPs are a subtype of PRFs, it is not unreasonable to believe that the latter can be used to construct the former. In particular, three pseudorandom functions with equal-length inputs and outputs can be used to construct a pseudorandom permutation whose block length is twice that of the original function, i.e .

This is purely a theoretical construct used solely for illustrative purposes and it is *not* utilised in practice.

To construct such a PRP from three such PRFs, we use several rounds of the so-called Feistel transformation. Our PRP begins by parsing its input as two separate strings by splitting it in half, i.e. and . It then invokes and XORs its output with to produce the value . Subsequently, the PRP calls the next pseudorandom function on and XORs its output with to produce the value . The penultimate step is to produce the value by invoking the third pseudorandom function on and XOR-ing its output with . Finally, our PRP outputs the concatenation of and .

fn PRP(input: str[2S]) -> str[2S]
{
	let x1 = input[0..S];
	let x2 = input[S..];
	
	let y1 = xor(f1(x2), x1);
	let y2 = xor(f2(y1), x2);
	
	let z = xor(f3(y2), y1);
	
	return z + y2;
}

All operations used are efficient and they are also used a fixed number of times for any input which means that this PRP is indeed efficient. Moreover, it is easily reversible simply by executing these operations in reverse order.

fn RevPRP(input: str[2S]) -> str[2S]
{
	let z = input[0..S];
	let y2 = input[S..];
	
	let y1 = xor(f3(y2), z);
	
	let x2 = xor(f2(y1), y2);
	let x1 = xor(f1(x2), y1);
	
	return x1 + x2;
}

The more arduous task is proving that this permutation is indeed pseudorandom.

TODO!

Pseudorandom Permutation Generator (PRPG)

Since PRPs are a subtype of PRFs and pseudorandom function generators (PRFGs) are a way to produce pseudorandom functions, we can reason about a restricted subtype of PRFGs which produce pseudorandom permutations.

A *pseudorandom permutation generator* $\textit{PRPG}(\textit{seed}: \textbf{str}[S]) \to \textbf{function<}\textbf{str}[S] \to \textbf{str}[S]\textbf{>}$ is a pseudorandom function generator which takes a seed $s \in \{0,1\}^S$ and outputs a pseudorandom permutation over $\{0,1\}^S$.

A PRPG is a PRFG for pseudorandom permutations. The block length of the PRPs produced by a given PRPG is the same as the length $S$ of the seed used for it.

As with PRFs, it is common to denote the function output by a PRPG for some particular seed $s$ as $\textit{PRP}_s$.

Similarly to PRFGs, it is important to remember that the output of a PRPG is still a function. Nevertheless, this did not stop mathematicians' folly before and it certainly will not stop it now - it is common to see a PRPG as a two input algorithm that takes a seed and an input data block and acts like a pseudorandom permutation . In this case, internally obtains the function from the seed and then passes it the data block . Finally, the PRPG returns the output of the permutation .

fn PRPG(seed: str[S], idb: str[S]) -> str[S] {
	let PRP = get_prp_from_seed(seed);
	return PRP(idb);
}